package com.zwj.interview.回溯;

import java.util.LinkedList;
import java.util.List;

/**
 * 题目：输入一个字符串，要求将它分割成若干子字符串，使每个子字符串都是回文。
 * 请列出所有可能的分割方法。例如，输入"google"，将输出3种符合条件的分割方法，
 * 分别是["g"，"o"，"o"，"g"，"l"，"e"]、["g"，"oo"，"g"，"l"，"e"]和["goog"，"l"，"e"]
 *
 * 回溯多看看
 */
public class 分割字符串成多个回文串 {

    List<List<String>> res = new LinkedList<>();

    public List<List<String>> partition(String s) {
        if (s == null || s.length() == 0) {
            return res;
        }
        helper(s, 0, new LinkedList<>(), res);
        return res;
    }

    private void helper(String str, int start, LinkedList<String> substrings, List<List<String>> result) {
        if (start == str.length()) {
            result.add(new LinkedList<>(substrings));
            return;
        }
        /**
         * 参数substrings是一组所有子字符串都是回文的分割。当处理到下标为start的字符串时，
         * 上述代码用一个for循环逐一判断从下标start开始到i结束（i从下标start开始，
         * 到字符串s的最后一个字符结束）的每个子字符串是否为回文。如果是回文，就分割出一个符合条件的子字符串，
         * 添加到substrings中，接着处理下标从i+1开始的剩余的字符串。当start等于字符串s的长度时，
         * 整个字符串s已经被分割成若干回文子字符串
         */
        for (int i = start; i < str.length(); ++i) {
            //逻辑
            if (isPalindrome(str, start, i)) {
                //路径中添加s[i]
                substrings.add(str.substring(start, i + 1));
                helper(str, i + 1, substrings, result);
                //撤销选择
                substrings.removeLast();
            }
        }
    }

    private boolean isPalindrome(String str, int start, int end) {
        while (start < end) {
            if (str.charAt(start++) != str.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
}
